using System;
using System.Collections.Generic;

public class CutLinkedList
{   
    //给你一个链表的头节点 head 和一个特定值 x ，
    //请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode(int val = 0, ListNode next = null)
        {
            this.val = val;
            this.next = next;
        }
    }

     public ListNode Partition(ListNode head, int x) {
        //两个分割的链表
        ListNode A = new (-1);
        ListNode B = new (-1);

        //两个链表的指针
        ListNode p1 = A;
        ListNode p2 = B;

        //循环遍历原来的链表
        while(head!=null){
            if(head.val<x){
                //A链表添加节点
                p1.next = head;
                //更新自身节点
                p1 = p1.next;
            }else{
                p2.next = head;
                p2 = p2.next;
            }
            head = head.next;
        }
        //断开B链表的最后一个节点
        p2.next =null;
        //连接两个链表
        p1.next = B.next;
        return A.next;
    }


}
